//#define _CRT_SECURE_NO_WARNINGS 1
//
//
//
//
//
//
//
//class Solution {
//public:
//    int integerReplacement(int n) {
//        double ret = 0;
//        ret = dfs(n);
//        return ret;
//    }
//    double dfs(long long n) {
//        if (n == 1) {
//            return 0;
//        }
//        if (n % 2 == 0) {
//            return 1 + dfs(n / 2);
//        }
//        else {
//            return 1 + min(dfs(n + 1), dfs(n - 1));
//        }
//    }
//};